package bTree.LeetCode;

import java.util.LinkedList;
import java.util.Queue;

public class 岛屿数量bfs {
    int[][] dir = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

    class pair{
        int x;
        int y;
        pair(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    public int numIslands(char[][] grid) {
        int row = grid.length, line = grid[0].length;
        int ans = 0;
        boolean[][] visited = new boolean[row][line];
        for(int i=0;i<row;i++){
            for (int j=0;j<line;j++){
                if(visited[i][j]==false&&grid[i][j]=='1'){
                    ans++;
                    bfs(grid,visited,i,j);
                }
            }
        }
        return ans;
    }

    private void bfs(char[][] grid, boolean[][] visited, int i, int j) {
        Queue<pair>queue=new LinkedList<>();
        queue.add(new pair(i,j));
        visited[i][j]=true;
        while (!queue.isEmpty()){
            for (int ii=0;ii<4;ii++){
                int nextX=queue.peek().x+dir[ii][0];
                int nextY=queue.peek().y+dir[ii][1];
                if(nextX<0||nextX>grid.length-1||nextY<0||nextY>grid[0].length-1){
                    continue;
                }
                if(visited[nextX][nextY]==false&&grid[nextX][nextY]=='1'){
                    queue.add(new pair(nextX,nextY));
                    visited[nextX][nextY]=true;
                }
            }
            queue.poll();
        }
    }
}